package leetcode.剑指offer.前40;

import org.junit.Test;

import java.util.Stack;

/**
 * @author :songyaozhang
 * @date :Created 2021/7/29 15:43
 * @description :https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/
 */
public class 剑指_31_栈的压入弹出序列 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.validateStackSequences(new int[]{1, 2, 3, 4, 5}, new int[]{4, 5, 3, 1, 2}));
    }


    class Solution {
        /*public boolean validateStackSequences(int[] pushed, int[] popped) {
            Stack<Integer> stack = new Stack<>();
            int i = 0, j = 0;
            while (j < popped.length) {
                while (stack.isEmpty() || stack.peek() != popped[j]) {
                    if (i >= popped.length) break;
                    stack.push(pushed[i++]);
                }
                if (i >= pushed.length && !stack.isEmpty() && stack.peek() != popped[j]) return false;
                while (j < popped.length && !stack.isEmpty() && stack.peek() == popped[j]) {
                    stack.pop();
                    j++;
                }
            }
            return true;
        }*/

        public boolean validateStackSequences(int[] pushed, int[] popped) {
            Stack<Integer> stack = new Stack<>();
            int i = 0;
            for (int num : pushed) {
                stack.push(num);
                while (!stack.isEmpty() && stack.peek() == popped[i]) {
                    stack.pop();
                    i++;
                }
            }
            return stack.isEmpty();
        }
    }
}
